#include "common.h"

vector<string> ans;
string tems;
vector<string> tele = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
void dfs(string d, int index)
{
	if (index == d.size())
	{
		ans.push_back(tems);
		return;
	}
	for (int i = 0; i < tele[d[index] - '2'].size(); i++)
	{
		tems += tele[d[index] - '2'][i];
		dfs(d, index + 1);
		tems.pop_back();
	}
}
vector<string> letterCombinations(string digits)
{
	if (digits.size() == 0)
	{
		return ans;
	}
	dfs(digits, 0);
	return ans;
}